package LeetCode热题HOT100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class p15三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        //双指针
        List< List<Integer> > res=new ArrayList<>();
        if (nums.length<=2) {
            return res;
        }

        Arrays.sort(nums);//对数组进行排序
        for (int i = 0; i <nums.length; i++) {
            if (nums[i]>0) {
                break;
            }

            if (i>0 && nums[i]==nums[i-1]) {
                continue;//去重
            }

            int left=i+1;
            int right=nums.length-1;
            while (left<right) {
                int sum=nums[i]+nums[left]+nums[right];

                if (sum>0) {
                    right--;
                }else if (sum<0) {
                    left++;
                }else {
                    //sum==0
                    res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //Arrays工具类提供了一个方法asList, 该方法可以将一个变长参数或者数组转换成List,这里传入的就是变长参数。
                    //这种方法创建的ArrayList不能进行add、set以及remove方法，因为参照源码可知 asList方法使用的ArrayList类是一个内部定义的类，而不是java.util.ArrayList类，
                    //而这个内部类继承了抽象类java.util.AbstractList<E>, 但是没有重写add和remove方法，没有给出具体的实现，
                    //而java.util.AbstractList类在add、set以及remove方法中，直接会抛出UnsupportedOperationException异常，
                    //所以为ava.util.Arrays类的内部类ArrayList调用add方法时，其实是调用了AbstractList类的add方法，结果就是直接抛出UnsupportedOperationException异常

                    while (left<right && nums[right]==nums[right-1]) right--;//去重
                    while (left<right && nums[left]==nums[left+1]) left++;//去重

                    right--;
                    left++;
                }
            }
        }

        return res;
    }
}
